package com.zzz.algorithm;

public class Kmp {


    private int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;
        int k = -1;
        next[0] = -1;
        for (; j < next.length - 1; ) {
            if (k == -1 || (pattern.charAt(j) == pattern.charAt(k))) {
                k++;
                j++;
                //pattern.charAt(j) == pattern.charAt(k) 相等可以继续滑动下一个
                if (pattern.charAt(j) == pattern.charAt(k)) {
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
                //next[++j] = k;

            } else {
                k = next[k];
            }
        }
        return next;
    }


    public int indexOf(String source, String target) {
        int[] next = getNext(target);
        char[] t = source.toCharArray();
        char[] p = target.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        while (i < t.length && j < p.length) {

            if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
                i++;
                j++;
            } else {
                j = next[j]; // j回到指定位置
            }
        }
        if (j == p.length) {
            return i - j;
        } else {
            return -1;
        }
    }


    public void test(String source, String target, int count) {
        //[-1, -1, 0, 1, -1, 0, 0, 1, 2]
        //[-1, 0, -1, 1, 0, 2, -1, 0, -1]
        for (int i = 0; i < count; i++) {
            indexOf(source, target);
        }
    }


}
